/*-------------------------------------------------------------------------
 *
 * nbtdedup.c
 *	  在 Postgres btree 中去重或自底向上删除项目。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/access/nbtree/nbtdedup.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/nbtree.h"
#include "access/nbtxlog.h"
#include "access/xloginsert.h"
#include "miscadmin.h"
#include "utils/rel.h"

static void fc__bt_bottomupdel_finish_pending(Page fc_page, BTDedupState fc_state,
										   TM_IndexDeleteOp *fc_delstate);
static bool fc__bt_do_singleval(Relation fc_rel, Page fc_page, BTDedupState fc_state,
							 OffsetNumber fc_minoff, IndexTuple fc_newitem);
static void fc__bt_singleval_fillfactor(Page fc_page, BTDedupState fc_state,
									 Size fc_newitemsz);
#ifdef USE_ASSERT_CHECKING
static bool fc__bt_posting_valid(IndexTuple fc_posting);
#endif

/*
 * 执行去重传递。
 *
 * 这里采取的总体方法是尽可能地进行去重，以释放尽可能多的空间。 然而，请注意，当页面充满了单一值的元组时，!bottomupdedup 调用者使用的“单值”策略。 应用该策略的去重传递将在页面末尾留下少数未处理的元组，为即将到来的页面拆分做好准备，该拆分使用 nbtsplitloc.c 自身的单值策略。 我们的高层次目标是延迟合并未处理的元组，直到页面拆分之后。
 *
 * 当调用 _bt_bottomupdel_pass() 刚刚发生（并且失败）时，我们的高层次目标是通过争取更多时间来完全防止页面拆分。 我们仍然希望能够完全避免页面拆分。 这就是为什么对 bottomupdedup 调用者甚至没有考虑单值策略。
 *
 * 如果我们无法成功释放至少 newitemsz（我们还需要为 newitem 的行指针留出空间，这不包括在调用者的 newitemsz 中），则页面必须被拆分。
 *
 * 注意：调用者应该已经删除了所有现有项目及其 LP_DEAD 位已设置。
 */
void _bt_dedup_pass(Relation fc_rel, Buffer fc_buf, Relation fc_heapRel, IndexTuple fc_newitem,
			   Size fc_newitemsz, bool fc_bottomupdedup)
{
	OffsetNumber fc_offnum,
				fc_minoff,
				fc_maxoff;
	Page		fc_page = BufferGetPage(fc_buf);
	BTPageOpaque fc_opaque = BTPageGetOpaque(fc_page);
	Page		fc_newpage;
	BTDedupState fc_state;
	Size		fc_pagesaving PG_USED_FOR_ASSERTS_ONLY = 0;
	bool		fc_singlevalstrat = false;
	int			fc_nkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_rel);

	/* 传入的 newitemsz 是 MAXALIGNED 但不包括行指针 */
	fc_newitemsz += sizeof(ItemIdData);

	/*
	 * 初始化去重状态。
	 *
	 * maxpostingsize（发布列表元组大小的限制）可以设置为页面的三分之一。 然而，限制发布列表的大小为页面的六分之一似乎是个好主意。 这样在充满重复的页面可以进行多次拆分时，应该能给我们留出一个好的拆分点。
	 */
	fc_state = (BTDedupState) palloc(sizeof(BTDedupStateData));
	fc_state->deduplicate = true;
	fc_state->nmaxitems = 0;
	fc_state->maxpostingsize = Min(BTMaxItemSize(fc_page) / 2, INDEX_SIZE_MASK);
	/* 关于当前待处理发布列表的基础元组的元数据 */
	fc_state->base = NULL;
	fc_state->baseoff = InvalidOffsetNumber;
	fc_state->basetupsize = 0;
	/* 关于当前待处理发布列表 TID 的元数据 */
	fc_state->htids = palloc(fc_state->maxpostingsize);
	fc_state->nhtids = 0;
	fc_state->nitems = 0;
	/* 将被待处理发布列表替换的所有物理元组的大小 */
	fc_state->phystupsize = 0;
	/* nintervals 应初始化为零 */
	fc_state->nintervals = 0;

	fc_minoff = P_FIRSTDATAKEY(fc_opaque);
	fc_maxoff = PageGetMaxOffsetNumber(fc_page);

	/*
	 * 考虑应用“单值”策略，但仅在页面似乎在不久的将来可能被拆分的情况下
	 */
	if (!fc_bottomupdedup)
		fc_singlevalstrat = fc__bt_do_singleval(fc_rel, fc_page, fc_state, fc_minoff, fc_newitem);

	/*
	 * 从页面中去重项目，并将它们写入 newpage。
	 *
	 * 将原始页面的 LSN 复制到 newpage 副本中。 这将成为页面的更新版本。 我们需要这样做，因为 XLogInsert 将检查 LSN 并可能将其转储到页面图像中。
	 */
	fc_newpage = PageGetTempPageCopySpecial(fc_page);
	PageSetLSN(fc_newpage, PageGetLSN(fc_page));

	/* 复制高键，如果有的话 */
	if (!P_RIGHTMOST(fc_opaque))
	{
		ItemId		fc_hitemid = PageGetItemId(fc_page, P_HIKEY);
		Size		fc_hitemsz = ItemIdGetLength(fc_hitemid);
		IndexTuple	fc_hitem = (IndexTuple) PageGetItem(fc_page, fc_hitemid);

		if (PageAddItem(fc_newpage, (Item) fc_hitem, fc_hitemsz, P_HIKEY,
						false, false) == InvalidOffsetNumber)
			elog(ERROR, "deduplication failed to add highkey");
	}

	for (fc_offnum = fc_minoff;
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);

		Assert(!ItemIdIsDead(fc_itemid));

		if (fc_offnum == fc_minoff)
		{
			/*
			 * 数据项没有以前/基础元组 -- 将数据项用作待处理发布列表的基础元组
			 */
			_bt_dedup_start_pending(fc_state, fc_itup, fc_offnum);
		}
		else if (fc_state->deduplicate &&
				 _bt_keep_natts_fast(fc_rel, fc_state->base, fc_itup) > fc_nkeyatts &&
				 _bt_dedup_save_htid(fc_state, fc_itup))
		{
			/*
			 * 元组等于待处理发布列表的基础元组。 它的 Heap TID(s) 已在状态中保存。
			 */
		}
		else
		{
			/*
			 * 元组不等于待处理的发布列表元组，或者
			 * _bt_dedup_save_htid() 选择不将当前项目合并到
			 * 待处理的发布列表中，出于其他原因（例如，添加更多
			 * TID 会导致发布列表超过当前的
			 * maxpostingsize）。
			 *
			 * 如果状态包含多个项目的待处理发布列表，
			 * 形成新的发布元组，并实际上更新页面。否则
			 * 重置状态，不对页面进行修改。
			 */
			fc_pagesaving += _bt_dedup_finish_pending(fc_newpage, fc_state);

			if (fc_singlevalstrat)
			{
				/*
				 * 单值策略的额外步骤。
				 *
				 * 在形成或观察到 5 个已有 maxpostingsize 限制的元组的
				 * 时刻，降低第六个也是最后一个大发布列表
				 * 元组的 maxpostingsize。
				 *
				 * 当形成/观察到第六个 maxpostingsize 限制的项目时，
				 * 完全停止合并元组。页面末尾剩下的少量元组
				 * 将根本不会合并在一起（至少在未来的页面拆分发生
				 * 之前不会合并）。
				 */
				if (fc_state->nmaxitems == 5)
					fc__bt_singleval_fillfactor(fc_page, fc_state, fc_newitemsz);
				else if (fc_state->nmaxitems == 6)
				{
					fc_state->deduplicate = false;
					fc_singlevalstrat = false; /* 不会再回到这里 */
				}
			}

			/* itup 开始新的待处理发布列表 */
			_bt_dedup_start_pending(fc_state, fc_itup, fc_offnum);
		}
	}

	/* 处理最后一项 */
	fc_pagesaving += _bt_dedup_finish_pending(fc_newpage, fc_state);

	/*
	 * 如果未找到适合去重的项目，则 newpage 必须
	 * 与原始页面完全相同，所以只需从函数中返回。
	 *
	 * 我们可以根据节省的空间是否足够以避免立即的页面拆分
	 * 来决定是否继续。我们不这样做，因为在 nbtsplitloc.c 中
	 * 总是针对一个完全去重的页面操作是有一点小价值的（除了
	 * newitem）。此外，大部分成本已经付出。
	 */
	if (fc_state->nintervals == 0)
	{
		/* 这里不能泄漏内存 */
		pfree(fc_newpage);
		pfree(fc_state->htids);
		pfree(fc_state);
		return;
	}

	/*
	 * 到这里，很明显去重肯定会继续进行。
	 *
	 * 清除 BTP_HAS_GARBAGE 页面标志。索引必须是一个 heapkeyspace
	 * 索引，因此我们无论如何都不会关注 BTP_HAS_GARBAGE。
	 * 但保持整洁。
	 */
	if (P_HAS_GARBAGE(fc_opaque))
	{
		BTPageOpaque fc_nopaque = BTPageGetOpaque(fc_newpage);

		fc_nopaque->btpo_flags &= ~BTP_HAS_GARBAGE;
	}

	START_CRIT_SECTION();

	PageRestoreTempPage(fc_newpage, fc_page);
	MarkBufferDirty(fc_buf);

	/* XLOG 相关内容 */
	if (RelationNeedsWAL(fc_rel))
	{
		XLogRecPtr	fc_recptr;
		xl_btree_dedup fc_xlrec_dedup;

		fc_xlrec_dedup.nintervals = fc_state->nintervals;

		XLogBeginInsert();
		XLogRegisterBuffer(0, fc_buf, REGBUF_STANDARD);
		XLogRegisterData((char *) &fc_xlrec_dedup, SizeOfBtreeDedup);

		/*
		 * intervals 数组不在缓冲区中，但假装它在。
		 * 当 XLogInsert 存储整个缓冲区时，数组不必被
		 * 存储。
		 */
		XLogRegisterBufData(0, (char *) fc_state->intervals,
							fc_state->nintervals * sizeof(BTDedupInterval));

		fc_recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DEDUP);

		PageSetLSN(fc_page, fc_recptr);
	}

	END_CRIT_SECTION();

	/* 本地空间会计应与页面会计一致 */
	Assert(fc_pagesaving < fc_newitemsz || PageGetExactFreeSpace(fc_page) >= fc_newitemsz);

	/* 这里不能泄漏内存 */
	pfree(fc_state->htids);
	pfree(fc_state);
}

/*
 * 执行自下而上的索引删除过程。
 *
 * 查看重复的索引元组（加上某些附近的元组）是否有资格
 * 通过自下而上的索引删除进行删除。这里的高层目标是
 * 完全防止由于更新导致的MVCC版本变化造成的"不必要"的页分裂
 * （当更新在逻辑上不修改任何由'rel'索引覆盖的列时）。这是一种定性，而不是定量——
 * 我们并不特别关心一次性机会以一起删除许多索引元组。
 *
 * 请参阅nbtree/README获取有关nbtree自下而上删除设计的详细信息。
 * 请参阅access/tableam.h以获取我们期望如何与tableam合作的描述。
 *
 * 成功时返回true，此时调用者可以假设在合理的时间内将避免页面分裂。
 * 当调用者应去重页面时返回false（如果可能的话）。
 *
 * 注意：偶尔我们在未能删除足够的项目以避免分裂的情况下返回true。
 * 这使得调用者跳过去重，立即去分裂页面。我们的返回值始终只是建议信息。
 *
 * 注意：调用者应该已经删除所有现有项，其LP_DEAD位已设置。
 */
bool _bt_bottomupdel_pass(Relation fc_rel, Buffer fc_buf, Relation fc_heapRel,
					 Size fc_newitemsz)
{
	OffsetNumber fc_offnum,
				fc_minoff,
				fc_maxoff;
	Page		fc_page = BufferGetPage(fc_buf);
	BTPageOpaque fc_opaque = BTPageGetOpaque(fc_page);
	BTDedupState fc_state;
	TM_IndexDeleteOp fc_delstate;
	bool		fc_neverdedup;
	int			fc_nkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_rel);

	/* 传入的 newitemsz 是 MAXALIGNED 但不包括行指针 */
	fc_newitemsz += sizeof(ItemIdData);

	/* 初始化去重状态 */
	fc_state = (BTDedupState) palloc(sizeof(BTDedupStateData));
	fc_state->deduplicate = true;
	fc_state->nmaxitems = 0;
	fc_state->maxpostingsize = BLCKSZ; /* 我们并不是在真正地去重 */
	fc_state->base = NULL;
	fc_state->baseoff = InvalidOffsetNumber;
	fc_state->basetupsize = 0;
	fc_state->htids = palloc(fc_state->maxpostingsize);
	fc_state->nhtids = 0;
	fc_state->nitems = 0;
	fc_state->phystupsize = 0;
	fc_state->nintervals = 0;

	/*
	 * 初始化描述自下而上索引删除操作的tableam状态。
	 *
	 * 我们将继续要求tableam搜索可以安全删除的索引元组的TID。
	 * tableam将搜索直到我们的叶子页面空间目标得到满足，或者继续进行tableam
	 * 操作的成本似乎太高。它将精力集中在与我们标记为“有前景”的重复索引元组相关的TID上。
	 *
	 * 这个空间目标有点任意。tableam必须能够保持成本和收益的平衡。
	 * 我们提供给tableam关于可能有效的信息，而不直接
	 * 关心在tableam调用期间避免工作的事情。我们在计成本的
	 * 自下而上删除过程中的角色是严格的建议性。
	 */
	fc_delstate.irel = fc_rel;
	fc_delstate.iblknum = BufferGetBlockNumber(fc_buf);
	fc_delstate.bottomup = true;
	fc_delstate.bottomupfreespace = Max(BLCKSZ / 16, fc_newitemsz);
	fc_delstate.ndeltids = 0;
	fc_delstate.deltids = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexDelete));
	fc_delstate.status = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexStatus));

	fc_minoff = P_FIRSTDATAKEY(fc_opaque);
	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_offnum = fc_minoff;
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);

		Assert(!ItemIdIsDead(fc_itemid));

		if (fc_offnum == fc_minoff)
		{
			/* itup开始第一个待定区间 */
			_bt_dedup_start_pending(fc_state, fc_itup, fc_offnum);
		}
		else if (_bt_keep_natts_fast(fc_rel, fc_state->base, fc_itup) > fc_nkeyatts &&
				 _bt_dedup_save_htid(fc_state, fc_itup))
		{
			/* 元组相等；只是将其TID添加到待定区间 */
		}
		else
		{
			/* 最终确定区间——将其TID移至删除状态 */
			fc__bt_bottomupdel_finish_pending(fc_page, fc_state, &fc_delstate);

			/* itup开始新的待定区间 */
			_bt_dedup_start_pending(fc_state, fc_itup, fc_offnum);
		}
	}
	/* 最终确定最终区间——将其TID移至删除状态 */
	fc__bt_bottomupdel_finish_pending(fc_page, fc_state, &fc_delstate);

	/*
	 * 如果tableam有很少（甚至没有）前景元组，我们现在并不放弃，
	 * 因为作为索引AM管理成本不是我们的责任（请注意，tableam可能有自己的启发式
	 * 方法来解决该问题）。不过，在存在零个前景元组的情况下，我们应该至少避免
	 * 让调用者在我们返回后进行无用的去重过程。
	 */
	fc_neverdedup = false;
	if (fc_state->nintervals == 0)
		fc_neverdedup = true;

	pfree(fc_state->htids);
	pfree(fc_state);

	/* 向 tableam 询问哪些 TID 可删除，然后物理删除它们 */
	_bt_delitems_delete_check(fc_rel, fc_buf, fc_heapRel, &fc_delstate);

	pfree(fc_delstate.deltids);
	pfree(fc_delstate.status);

	/* 无条件向调用者报告“成功”，以避免重复去重 */
	if (fc_neverdedup)
		return true;

	/* 当我们不会很快回来时，不要去重 */
	return PageGetExactFreeSpace(fc_page) >= Max(BLCKSZ / 24, fc_newitemsz);
}

/*
 * 根据调用者的基本元组创建一个新的待处理发布列表元组。
 *
 * 由去重处理的每个元组要么成为发布列表的基本元组，要么将其堆 TID 接收进入待处理发布列表。
 * 开始时作为发布列表的基本元组的元组，只有在发现可以合并到基本元组的重复项时，才会在 _bt_dedup_finish_pending() 中实际重写。
 */
void _bt_dedup_start_pending(BTDedupState fc_state, IndexTuple fc_base,
						OffsetNumber fc_baseoff)
{
	Assert(fc_state->nhtids == 0);
	Assert(fc_state->nitems == 0);
	Assert(!BTreeTupleIsPivot(fc_base));

	/*
	 * 从新的基本元组中复制堆 TID 以用于新的候选发布列表
	 * 到工作状态的数组中
	 */
	if (!BTreeTupleIsPosting(fc_base))
	{
		memcpy(fc_state->htids, &fc_base->t_tid, sizeof(ItemPointerData));
		fc_state->nhtids = 1;
		fc_state->basetupsize = IndexTupleSize(fc_base);
	}
	else
	{
		int			fc_nposting;

		fc_nposting = BTreeTupleGetNPosting(fc_base);
		memcpy(fc_state->htids, BTreeTupleGetPosting(fc_base),
			   sizeof(ItemPointerData) * fc_nposting);
		fc_state->nhtids = fc_nposting;
		/* basetupsize 不应包含现有的发布列表 */
		fc_state->basetupsize = BTreeTupleGetPostingOffset(fc_base);
	}

	/*
	 * 保存新的基本元组本身——如果我们实际从新的待处理发布列表创建新发布列表，它将是必需的。
	 *
	 * 必须维护所有现有元组的物理大小（包括行指针开销），以便我们可以计算页面上的节省空间。
	 */
	fc_state->nitems = 1;
	fc_state->base = fc_base;
	fc_state->baseoff = fc_baseoff;
	fc_state->phystupsize = MAXALIGN(IndexTupleSize(fc_base)) + sizeof(ItemIdData);
	/* 还要在待处理状态中保存基偏移以用于间隔 */
	fc_state->intervals[fc_state->nintervals].baseoff = fc_state->baseoff;
}

/*
 * 将 itup 的堆 TID 保存到待处理发布列表中（如可能）。
 *
 * 返回 bool 值，指示状态管理的待处理发布列表是否现在包含了 itup 的堆 TID。
 */
bool _bt_dedup_save_htid(BTDedupState fc_state, IndexTuple fc_itup)
{
	int			fc_nhtids;
	ItemPointer fc_htids;
	Size		fc_mergedtupsz;

	Assert(!BTreeTupleIsPivot(fc_itup));

	if (!BTreeTupleIsPosting(fc_itup))
	{
		fc_nhtids = 1;
		fc_htids = &fc_itup->t_tid;
	}
	else
	{
		fc_nhtids = BTreeTupleGetNPosting(fc_itup);
		fc_htids = BTreeTupleGetPosting(fc_itup);
	}

	/*
	 * 如果将 itup 的堆 TID 追加到待处理发布列表会使我们超出 maxpostingsize 限制，则不要追加（让调用者按原样完成待处理发布列表）。
	 *
	 * 此计算需要与 _bt_form_posting() 中用于新的发布列表元组的代码匹配。
	 */
	fc_mergedtupsz = MAXALIGN(fc_state->basetupsize +
						   (fc_state->nhtids + fc_nhtids) * sizeof(ItemPointerData));

	if (fc_mergedtupsz > fc_state->maxpostingsize)
	{
		/*
		 * 将此计入单值策略的超大项，尽管仅当最终发布列表元组中有 50 个 TID 时。这一限制（相当任意）避免了关于当前去重遍历已经遇到/创建了多少 1/6 页面元组的混淆。
		 *
		 * 注意：我们故意不考虑哪个去重遍历合并元组以创建此项（可能是以前的去重遍历或当前遍历）。参见 _bt_do_singleval() 的注释。
		 */
		if (fc_state->nhtids > 50)
			fc_state->nmaxitems++;

		return false;
	}

	/*
	 * 将堆 TID 保存到待处理发布列表元组——itup 可以合并到待处理发布列表
	 */
	fc_state->nitems++;
	memcpy(fc_state->htids + fc_state->nhtids, fc_htids,
		   sizeof(ItemPointerData) * fc_nhtids);
	fc_state->nhtids += fc_nhtids;
	fc_state->phystupsize += MAXALIGN(IndexTupleSize(fc_itup)) + sizeof(ItemIdData);

	return true;
}

/*
 * 最终待处理发布列表元组，并将其添加到页面。最终元组基于保存的基本元组和保存的堆 TID 列表。
 *
 * 返回通过去重生成新的发布列表元组而节省的空间。注意，这包括行指针的开销。当没有进行任何去重时，这个值为零。
 */
Size _bt_dedup_finish_pending(Page fc_newpage, BTDedupState fc_state)
{
	OffsetNumber fc_tupoff;
	Size		fc_tuplesz;
	Size		fc_spacesaving;

	Assert(fc_state->nitems > 0);
	Assert(fc_state->nitems <= fc_state->nhtids);
	Assert(fc_state->intervals[fc_state->nintervals].baseoff == fc_state->baseoff);

	fc_tupoff = OffsetNumberNext(PageGetMaxOffsetNumber(fc_newpage));
	if (fc_state->nitems == 1)
	{
		/* 使用原始、未更改的基本元组 */
		fc_tuplesz = IndexTupleSize(fc_state->base);
		if (PageAddItem(fc_newpage, (Item) fc_state->base, fc_tuplesz, fc_tupoff,
						false, false) == InvalidOffsetNumber)
			elog(ERROR, "deduplication failed to add tuple to page");

		fc_spacesaving = 0;
	}
	else
	{
		IndexTuple	fc_final;

		/* 使用发布列表形成一个元组 */
		fc_final = _bt_form_posting(fc_state->base, fc_state->htids, fc_state->nhtids);
		fc_tuplesz = IndexTupleSize(fc_final);
		Assert(fc_tuplesz <= fc_state->maxpostingsize);

		/* 保存发布列表的最终项目数 */
		fc_state->intervals[fc_state->nintervals].nitems = fc_state->nitems;

		Assert(fc_tuplesz == MAXALIGN(IndexTupleSize(fc_final)));
		if (PageAddItem(fc_newpage, (Item) fc_final, fc_tuplesz, fc_tupoff, false,
						false) == InvalidOffsetNumber)
			elog(ERROR, "deduplication failed to add tuple to page");

		pfree(fc_final);
		fc_spacesaving = fc_state->phystupsize - (fc_tuplesz + sizeof(ItemIdData));
		/* 增加 nintervals，因为我们写入了一个新的发布列表元组 */
		fc_state->nintervals++;
		Assert(fc_spacesaving > 0 && fc_spacesaving < BLCKSZ);
	}

	/* 重置状态以便下一个待处理发布列表 */
	fc_state->nhtids = 0;
	fc_state->nitems = 0;
	fc_state->phystupsize = 0;

	return fc_spacesaving;
}

/*
 * 在自底向上的索引删除过程中完成区间的最终确定。
 *
 * 在自底向上的遍历中，我们预期 TIDs 将首先记录在去重状态中，
 * 然后通过此处调用以可变大小的批次移至 delstate。此处的调用发生在
 * 去重区间中的 TIDs 数量已知时，区间被最终确定（即当调用者在页面上看到
 * 下一个元组不是重复时，或者当调用者处理完来自叶子页面的元组时）。
 *
 * 这是自底向上删除确定并记住哪些条目是重复的地方。这将是对
 * tableam 删除基础设施的重要信息。在这里，普通索引元组的重复项被标记为
 * "有希望的"，根据 tableam 合同。
 *
 * 我们标记来自发布列表的条目的方法更加复杂。发布列表只能通过
 * 去重遍历（或在索引构建期间）形成，因此影响指向的逻辑行的
 * 最近版本变动不太可能发生。我们可能仍会对发布列表元组的条目发出
 * 微弱信号（通过仅标记其 TID/条目之一为有希望的），尽管这只有在
 * 覆盖发布列表元组的最终区间中存在进一步重复的索引元组的情况下
 * 才是可能的（如在普通元组情况下）。当 tableam 在整体删除操作中
 * 没有更强信号可供参考时，微弱信号/提示将是有用的。
 *
 * 我们使用的启发式方法在实践中效果良好，因为我们只需要给
 * tableam 提供正确的 _一般_ 思路，告诉其去哪里查找。垃圾倾向于
 * 在自底向上删除目标的工作负载中自然集中在相对少数的表块中。
 * tableam 不可能基于我们提供的提示对所有可用的表块进行合理排名，
 * 但这没关系——只有极端情况重要。tableam 只需能够预测每个删除
 * 操作中将有多少个元组是安全删除的，并且在相关的删除操作之间保持
 * 低方差即可。
 */
static void fc__bt_bottomupdel_finish_pending(Page fc_page, BTDedupState fc_state,
							   TM_IndexDeleteOp *fc_delstate)
{
	bool		fc_dupinterval = (fc_state->nitems > 1);

	Assert(fc_state->nitems > 0);
	Assert(fc_state->nitems <= fc_state->nhtids);
	Assert(fc_state->intervals[fc_state->nintervals].baseoff == fc_state->baseoff);

	for (int fc_i = 0; fc_i < fc_state->nitems; fc_i++)
	{
		OffsetNumber fc_offnum = fc_state->baseoff + fc_i;
		ItemId		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);
		TM_IndexDelete *fc_ideltid = &fc_delstate->deltids[fc_delstate->ndeltids];
		TM_IndexStatus *fc_istatus = &fc_delstate->status[fc_delstate->ndeltids];

		if (!BTreeTupleIsPosting(fc_itup))
		{
			/* 简单情况：一个普通的非轴元组 */
			fc_ideltid->tid = fc_itup->t_tid;
			fc_ideltid->id = fc_delstate->ndeltids;
			fc_istatus->idxoffnum = fc_offnum;
			fc_istatus->knowndeletable = false;	/* 目前为止 */
			fc_istatus->promising = fc_dupinterval;	/* 简单规则 */
			fc_istatus->freespace = ItemIdGetLength(fc_itemid) + sizeof(ItemIdData);

			fc_delstate->ndeltids++;
		}
		else
		{
			/*
			 * 复杂情况：一个发布列表元组。
			 *
			 * 我们做出保守假设，即每个发布列表元组至多只能有一个
			 * 受影响的逻辑行。在 deltids 中至多会有一个有希望的条目
			 * 来代表这个假定的孤立逻辑行。请注意，只有在发布列表元组
			 * 也在重复区间中时才会考虑这一点——这一复杂规则只是用来
			 * 决定普通索引元组是否有前景的简单规则的一种变体。
			 */
			int			fc_nitem = BTreeTupleGetNPosting(fc_itup);
			bool		fc_firstpromising = false;
			bool		fc_lastpromising = false;

			Assert(fc__bt_posting_valid(fc_itup));

			if (fc_dupinterval)
			{
				/*
				 * 复杂规则：发布列表中的第一个或最后一个 TID 被标记为
				 * 有希望的（如果有的话）
				 */
				BlockNumber fc_minblocklist,
							fc_midblocklist,
							fc_maxblocklist;
				ItemPointer fc_mintid,
							fc_midtid,
							fc_maxtid;

				fc_mintid = BTreeTupleGetHeapTID(fc_itup);
				fc_midtid = BTreeTupleGetPostingN(fc_itup, fc_nitem / 2);
				fc_maxtid = BTreeTupleGetMaxHeapTID(fc_itup);
				fc_minblocklist = ItemPointerGetBlockNumber(fc_mintid);
				fc_midblocklist = ItemPointerGetBlockNumber(fc_midtid);
				fc_maxblocklist = ItemPointerGetBlockNumber(fc_maxtid);

				/* 只有占主导地位的表块中的条目才能被标记为有希望的 */
				fc_firstpromising = (fc_minblocklist == fc_midblocklist);
				fc_lastpromising = (!fc_firstpromising &&
								 fc_midblocklist == fc_maxblocklist);
			}

			for (int fc_p = 0; fc_p < fc_nitem; fc_p++)
			{
				ItemPointer fc_htid = BTreeTupleGetPostingN(fc_itup, fc_p);

				fc_ideltid->tid = *fc_htid;
				fc_ideltid->id = fc_delstate->ndeltids;
				fc_istatus->idxoffnum = fc_offnum;
				fc_istatus->knowndeletable = false;	/* 目前为止 */
				fc_istatus->promising = false;
				if ((fc_firstpromising && fc_p == 0) ||
					(fc_lastpromising && fc_p == fc_nitem - 1))
					fc_istatus->promising = true;
				fc_istatus->freespace = sizeof(ItemPointerData);	/* 清理状态以便下一区间使用 */

				fc_ideltid++;
				fc_istatus++;
				fc_delstate->ndeltids++;
			}
		}
	}

	if (fc_dupinterval)
	{
		fc_state->intervals[fc_state->nintervals].nitems = fc_state->nitems;
		fc_state->nintervals++;
	}

	/*
 * 确定页面非支点元组（数据项）是否都是同一值的重复项——如果是，去重的“单值”策略应该被应用。这个策略的一般目标是确保 nbtsplitloc.c（它使用自己的单值策略）在进一步插入重复项时能够找到一个有用的分割点，并且在存储相同重复值的页面之间发生连续的最右侧页面分割。当页面最终分割时，它应该充满 BTREE_SINGLEVAL_FILLFACTOR% 的容量，就像在去重被禁用时一样。
 *
 * 我们预计受影响的工作负载将在页面最终分割之前需要进行 _几次_ 单值策略去重的遍历（在只存储重复项的页面上）。第一次去重遍历应该只会找到常规的非支点元组。后续的去重遍历将找到现有的 maxpostingsize 限制的发布列表元组，这些元组必须被跳过。倒数第二次遍历通常是第一次实际达到 _bt_singleval_fillfactor() 的遍历，因此会故意留下几个未触及的非支点元组。最后一次去重遍历不会释放任何空间——它会跳过所有内容而不合并任何东西（它重走了倒数第二次遍历的步骤）。
 *
 * 幸运的是，进行几次遍历并不是太昂贵。每次遍历（第一次遍历之后）不会在前几次遍历留下的大型发布列表元组上消耗很多循环。每次遍历会在页面末尾找到一大块连续的小型重复元组进行合并。
 */
	fc_state->nhtids = 0;
	fc_state->nitems = 0;
	fc_state->phystupsize = 0;
}

/*
 * 在使用“单值”策略时降低 maxpostingsize，以避免第六个
 * 也是最后一个 maxpostingsize 限制的元组。第六个
 * 也是最后一个发布列表元组将会比前五个小一些。（注意：前五个元组实际上可能只是非常大的重复元组，根本无法合并。在这种情况下，去重将不会对页面进行任何修改。）
 *
 * 当页面上有六个发布列表（在当前去重遍历后创建/观察到第六个非常大的元组）时，调用者应该结束其去重遍历。试图去重那些应该在预期的页面分割后进入新右兄弟页面的项目是没有意义的。未来的右兄弟页面的去重遍历可能会处理它。（这就是为什么给定叶页面的第一次单值策略去重遍历通常只会找到普通的非支点元组——参见 _bt_do_singleval() 注释。）
 */
static bool fc__bt_do_singleval(Relation fc_rel, Page fc_page, BTDedupState fc_state,
				 OffsetNumber fc_minoff, IndexTuple fc_newitem)
{
	int			fc_nkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_rel);
	ItemId		fc_itemid;
	IndexTuple	fc_itup;

	fc_itemid = PageGetItemId(fc_page, fc_minoff);
	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);

	if (_bt_keep_natts_fast(fc_rel, fc_newitem, fc_itup) > fc_nkeyatts)
	{
		fc_itemid = PageGetItemId(fc_page, PageGetMaxOffsetNumber(fc_page));
		fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);

		if (_bt_keep_natts_fast(fc_rel, fc_newitem, fc_itup) > fc_nkeyatts)
			return true;
	}

	return false;
}

/* 该计算需要匹配 nbtsplitloc.c */
static void fc__bt_singleval_fillfactor(Page fc_page, BTDedupState fc_state, Size fc_newitemsz)
{
	Size		fc_leftfree;
	int			fc_reduction;

	/* 减去新的高键的大小（包括支点堆 TID 空间） */
	fc_leftfree = PageGetPageSize(fc_page) - SizeOfPageHeaderData -
		MAXALIGN(sizeof(BTPageOpaqueData));
	/*
	 * 将 maxpostingsize 减少等于页面左半部分的目标空闲空间
	 */
	fc_leftfree -= fc_newitemsz + MAXALIGN(sizeof(ItemPointerData));

	/*
 * 根据调用者的“基础”索引元组和堆 TID 列表构建一个发布列表元组。
 * 当 nhtids == 1 时，构建一个标准的非支点元组，没有发布列表。
 * （发布列表元组永远不会只有一个堆 TID，部分原因是这可以确保去重始终减小整个元组的最终 MAXALIGN() 大小。）
 *
 * 约定是发布列表以 MAXALIGN() 对齐的偏移量开始（而不是 SHORTALIGN() 对齐的偏移量），这与在后缀截断期间将堆 TID 附加到新支点元组/高键时采取的方法一致。
 * 这有时会浪费一些仅在原始元组中需要作为对齐填充的空间。遵循此约定简化了去重页面时使用的空间计算（同样的约定简化了选择拆分页面的点的计算）。
 *
 * 注意：调用者的 “htids” 数组必须唯一且已经按升序 TID 排序。“base”中的任何现有堆 TIDs 不会自动出现在返回的发布列表元组中（它们必须包含在 htids 数组中。）
 */
	fc_reduction = fc_leftfree * ((100 - BTREE_SINGLEVAL_FILLFACTOR) / 100.0);
	if (fc_state->maxpostingsize > fc_reduction)
		fc_state->maxpostingsize -= fc_reduction;
	else
		fc_state->maxpostingsize = 0;
}

/* 确定新元组的最终大小 */
IndexTuple _bt_form_posting(IndexTuple fc_base, ItemPointer fc_htids, int fc_nhtids)
{
	uint32		fc_keysize,
				fc_newsize;
	IndexTuple	fc_itup;

	if (BTreeTupleIsPosting(fc_base))
		fc_keysize = BTreeTupleGetPostingOffset(fc_base);
	else
		fc_keysize = IndexTupleSize(fc_base);

	Assert(!BTreeTupleIsPivot(fc_base));
	Assert(fc_nhtids > 0 && fc_nhtids <= PG_UINT16_MAX);
	Assert(fc_keysize == MAXALIGN(fc_keysize));

	/* 使用 palloc0() 分配内存（与 index_form_tuple() 匹配） */
	if (fc_nhtids > 1)
		fc_newsize = MAXALIGN(fc_keysize +
						   fc_nhtids * sizeof(ItemPointerData));
	else
		fc_newsize = fc_keysize;

	Assert(fc_newsize <= INDEX_SIZE_MASK);
	Assert(fc_newsize == MAXALIGN(fc_newsize));

	/* 形成发布列表元组 */
	fc_itup = palloc0(fc_newsize);
	memcpy(fc_itup, fc_base, fc_keysize);
	fc_itup->t_info &= ~INDEX_SIZE_MASK;
	fc_itup->t_info |= fc_newsize;
	if (fc_nhtids > 1)
	{
		/* 形成标准非支点元组 */
		BTreeTupleSetPosting(fc_itup, fc_nhtids, fc_keysize);
		memcpy(BTreeTupleGetPosting(fc_itup), fc_htids,
			   sizeof(ItemPointerData) * fc_nhtids);
		Assert(fc__bt_posting_valid(fc_itup));
	}
	else
	{
		/*
 * 通过“更新”发布列表元组生成一个替代元组，以便它不再包含需要删除的 TID。
 *
 * 被 VACUUM 和索引删除用。调用者的 vacposting 参数指向要更新的现有发布列表元组。
 *
 * 返回时，调用者的 vacposting 参数将指向最终的“更新”元组，该元组将在调用者的内存上下文中分配内存。
 */
		fc_itup->t_info &= ~INDEX_ALT_TID_MASK;
		ItemPointerCopy(fc_htids, &fc_itup->t_tid);
		Assert(ItemPointerIsValid(&fc_itup->t_tid));
	}

	return fc_itup;
}

/*
	 * 确定新元组的最终大小。
	 *
	 * 此计算需要与 _bt_form_posting() 中用于新发布列表元组的代码相匹配。
	 * 我们避免在此处调用 _bt_form_posting() 以节省一个用于 htids 工作区的第二次内存分配。
	 */
void _bt_update_posting(BTVacuumPosting fc_vacposting)
{
	IndexTuple	fc_origtuple = fc_vacposting->itup;
	uint32		fc_keysize,
				fc_newsize;
	IndexTuple	fc_itup;
	int			fc_nhtids;
	int			fc_ui,
				fc_d;
	ItemPointer fc_htids;

	fc_nhtids = BTreeTupleGetNPosting(fc_origtuple) - fc_vacposting->ndeletedtids;

	Assert(fc__bt_posting_valid(fc_origtuple));
	Assert(fc_nhtids > 0 && fc_nhtids < BTreeTupleGetNPosting(fc_origtuple));

	/* 使用 palloc0() 分配内存（与 index_form_tuple() 匹配） */
	fc_keysize = BTreeTupleGetPostingOffset(fc_origtuple);
	if (fc_nhtids > 1)
		fc_newsize = MAXALIGN(fc_keysize +
						   fc_nhtids * sizeof(ItemPointerData));
	else
		fc_newsize = fc_keysize;

	Assert(fc_newsize <= INDEX_SIZE_MASK);
	Assert(fc_newsize == MAXALIGN(fc_newsize));

	/* 形成发布列表元组 */
	fc_itup = palloc0(fc_newsize);
	memcpy(fc_itup, fc_origtuple, fc_keysize);
	fc_itup->t_info &= ~INDEX_SIZE_MASK;
	fc_itup->t_info |= fc_newsize;

	if (fc_nhtids > 1)
	{
		/* 形成标准非支点元组 */
		BTreeTupleSetPosting(fc_itup, fc_nhtids, fc_keysize);
		fc_htids = BTreeTupleGetPosting(fc_itup);
	}
	else
	{
		/*
 * 通过“更新”发布列表元组生成一个替代元组，以便它不再包含需要删除的 TID。
 *
 * 被 VACUUM 和索引删除用。调用者的 vacposting 参数指向要更新的现有发布列表元组。
 *
 * 返回时，调用者的 vacposting 参数将指向最终的“更新”元组，该元组将在调用者的内存上下文中分配内存。
 */
		fc_itup->t_info &= ~INDEX_ALT_TID_MASK;
		fc_htids = &fc_itup->t_tid;
	}

	fc_ui = 0;
	fc_d = 0;
	for (int fc_i = 0; fc_i < BTreeTupleGetNPosting(fc_origtuple); fc_i++)
	{
		if (fc_d < fc_vacposting->ndeletedtids && fc_vacposting->deletetids[fc_d] == fc_i)
		{
			fc_d++;
			continue;
		}
		fc_htids[fc_ui++] = *BTreeTupleGetPostingN(fc_origtuple, fc_i);
	}
	Assert(fc_ui == fc_nhtids);
	Assert(fc_d == fc_vacposting->ndeletedtids);
	Assert(fc_nhtids == 1 || fc__bt_posting_valid(fc_itup));
	Assert(fc_nhtids > 1 || ItemPointerIsValid(&fc_itup->t_tid));

	/*
 * 通过将新项的堆 TID 与原始发布列表中的堆 TID（位于 'postingoff' 偏移量的 'oposting' 堆 TID）交换来准备发布列表分割。
 * 修改 newitem，因此调用者应该传递他们自己的私有副本，该副本可以安全修改。
 *
 * 返回新的发布列表元组，该元组在调用者的上下文中使用 palloc() 分配。
 * 保证与 'oposting' 的大小相同。修改后的 newitem 是调用者实际插入的内容。 
 * （这是在同一关键部分内发生的，该关键部分使用此处返回的新发布列表对旧发布列表执行就地更新。）
 *
 * 虽然 newitem 和 oposting 的键必须是 opclass 相等的，并且在通过底层类型的输出函数运行时必须生成相同的输出，但并不能因此认为它们的表示是完全匹配的。
 * 调用者必须避免假设存在表示差异，这可能导致 oposting 的数据项比 newitem 的相应数据项大或小。
 * 例如，TOAST 输入状态的差异可能会破坏对元组大小的错误假设（执行器有权根据自己的标准应用 TOAST 压缩）。
 * 似乎还有可能在未来引入更多的表示变异，以支持类似页面级前缀压缩的 nbtree 特性。
 *
 * 有关发布列表分割设计的详细信息，请参见 nbtree/README。
 */
	fc_vacposting->itup = fc_itup;
}

/*
	 * postingoff 参数起初是 _bt_binsrch_posting() 的返回值。
	 * 如果由于损坏使得一个叶页面包含一个与 newitem 以某种方式相同的非支点元组，则它将为 0（两个非支点元组不应该有相同的 TID）。
	 * 已知在实际应用中，这种情况偶尔会发生。
	 *
	 * 现在执行基本的完整性检查以捕捉此情况。
	 */
IndexTuple _bt_swap_posting(IndexTuple fc_newitem, IndexTuple fc_oposting, int fc_postingoff)
{
	int			fc_nhtids;
	char	   *fc_replacepos;
	char	   *fc_replaceposright;
	Size		fc_nmovebytes;
	IndexTuple	fc_nposting;

	fc_nhtids = BTreeTupleGetNPosting(fc_oposting);
	Assert(fc__bt_posting_valid(fc_oposting));

	/*
	 * 将发布列表中的项指针移动以为新项的堆 TID 留出空隙。
	 * 我们将 TID 向右移动一个位置，失去原始最右 TID。（nmovebytes 不能包括在 postingoff 左侧的 TID，也不能包括被覆盖的现有最右/max TID。）
	 */
	if (!(fc_postingoff > 0 && fc_postingoff < fc_nhtids))
		elog(ERROR, "posting list tuple with %d items cannot be split at offset %d",
			 fc_nhtids, fc_postingoff);

	/* 用新项的 TID（原始新 TID）填充 postingoff 的空隙 */
	fc_nposting = CopyIndexTuple(fc_oposting);
	fc_replacepos = (char *) BTreeTupleGetPostingN(fc_nposting, fc_postingoff);
	fc_replaceposright = (char *) BTreeTupleGetPostingN(fc_nposting, fc_postingoff + 1);
	fc_nmovebytes = (fc_nhtids - fc_postingoff - 1) * sizeof(ItemPointerData);
	memmove(fc_replaceposright, fc_replacepos, fc_nmovebytes);

	/* 现在将 oposting 的最右/max TID 复制到新项中（最终新 TID） */
	Assert(!BTreeTupleIsPivot(fc_newitem) && !BTreeTupleIsPosting(fc_newitem));
	ItemPointerCopy(&fc_newitem->t_tid, (ItemPointer) fc_replacepos);

	/*
 * 验证 "posting" 的发布列表不变性，该发布列表必须是一个发布列表元组。
 * 在断言中使用。
 */
	ItemPointerCopy(BTreeTupleGetMaxHeapTID(fc_oposting), &fc_newitem->t_tid);

	Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(fc_nposting),
							  BTreeTupleGetHeapTID(fc_newitem)) < 0);
	Assert(fc__bt_posting_valid(fc_nposting));

	return fc_nposting;
}

/* 记住循环的第一个堆 TID */
#ifdef USE_ASSERT_CHECKING
static bool fc__bt_posting_valid(IndexTuple fc_posting)
{
	ItemPointerData fc_last;
	ItemPointer fc_htid;

	if (!BTreeTupleIsPosting(fc_posting) || BTreeTupleGetNPosting(fc_posting) < 2)
		return false;

	/* 从第二个 TID 开始迭代 */
	ItemPointerCopy(BTreeTupleGetHeapTID(fc_posting), &fc_last);
	if (!ItemPointerIsValid(&fc_last))
		return false;

	/* Iterate, starting from second TID */
	for (int fc_i = 1; fc_i < BTreeTupleGetNPosting(fc_posting); fc_i++)
	{
		fc_htid = BTreeTupleGetPostingN(fc_posting, fc_i);

		if (!ItemPointerIsValid(fc_htid))
			return false;
		if (ItemPointerCompare(fc_htid, &fc_last) <= 0)
			return false;
		ItemPointerCopy(fc_htid, &fc_last);
	}

	return true;
}
#endif
